DP B
from 動的計画法
DP_B
まずは配るDP
code:python
def solve(N, K, heights):
heights += INF * K
costs = INF * (N + K)
costs0 = 0
for i in range(N - 1):
for k in range(1, K + 1):
costsi + k = min(
costsi + k,
costsi + abs(heightsi + k - heightsi))
return costsN - 1
ところが3TLE
下記のように関数呼び出しを削ったが1TLE残った
Numbaでコンパイルしようかと思ったが
PyPyで提出、165msec AC
code:python
def solve(N, K, heights):
heights += INF * K
costs = INF * (N + K)
costs0 = 0
for i in range(N - 1):
for k in range(1, K + 1):
newcost = costsi + abs(heightsi + k - heightsi)
if newcost < costsi + k:
costsi + k = newcost
return costsN - 1
集めるDP、
1625 ms AC
PyPy 385 ms
code:python
def solve(N, K, heights):
costs = 0 * N
costs0 = 0
for i in range(1, N):
costsi = min(
costsj + abs(heightsi - heightsj)
for j in range(max(i - K, 0), i)
)
8TLE
PyPy 540 ms AC
code:python
def solve(N, K, heights):
costs = None * N
costs0 = 0
def get_cost(i):
if costsi != None:
return costsi
c = min(
get_cost(j) + abs(heightsi - heightsj)
for j in range(max(i - K, 0), i)
)
costsi = c
return c
return get_cost(N - 1)